---
id: unit5
title: 第五章 死锁
---
## 死锁的产生
死锁是指在多道程序系统中的一种现象，一组进程中的每一个进程均无限期地等待被该组进程中的另一个进程所占有且永远不会释放的资源。系统发生这种现象称为系统处于死锁状态，简称死锁。处于死锁状态的进程称为死锁进程。

**死锁产生的原因：**  
（1）竞争资源  
系统资源在分配时出现失误，进程间对资源的相互争夺而造成僵局。死锁是若干进程因使用资源不当而造成无法推进的现象。
按照资源的使用性质，一般把系统中的资源分成两类：
永久性资源（可重用资源），是指系统中可供进程重复使用、长期存在的资源，如内存、外部设备、处理器等硬件资源，以及各种数据文件、表格、共享程序代码等软件资源；
临时性资源（消耗性资源），是指由某个进程所产生、只为另一个进程使用一次或经过短暂时间后便不再使用的资源。以上两种资源都可能导致死锁发生。  
（2）多道程序运行时，进程推进顺序不合理。  

**死锁产生的必要条件：**  
（1）互斥条件。  
（2）不可剥夺条件。  
（3）请求和保持条件。  
（4）循环等待条件。 

**解决死锁的方法：**  
预防死锁、避免死锁、检测与解除死锁、忽略死锁。

## 死锁预防
死锁预防是指在任何系统操作前（例如分配资源、调度进程等），事先评估系统的可能情况，严格采取措施使得死锁的四个必要条件不成立。死锁预防的基本思想是防范于未然。  
**预防死锁的策略：**  
（1）资源的静态分配策略。  
（2）资源的有序分配法：采用资源有序分配策略，其基本思想是将系统中所有资源顺序编号。一般原则是，较为紧缺、稀少的资源的编号较大。进程申请资源时，必须严格按
照资源编号的顺序进行，否则系统不予分配。即一个进程只有得到编号小的资源，才能申请编号较大的资源；释放资源时，应按编号递减的次序进行。

## 死锁避免
**死锁避免的基本思想是：**  
系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配。这是一种保证系统不进入死锁状态的动态策略。

**安全状态与不安全状态：**  
安全状态是指，如果存在一个由系统中所有进程构成的安全序列｛P1，···，Pn｝，则系统处于安全状态。一个进程序列｛P1，，Pn｝是安全的，如果对于其中每一个进程P；（1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程P；（j＜i）当前占有资源量之和。系统处于安全状态则不会发生死锁。如果不存在任何一个安全序列，则系统处于不安全状态。不安全状态不一定导致死锁，但死锁状态一定是不安全状态。即系统若处于不安全状态则可能发生死锁。

**银行家算法：**  
最著名的死锁避免算法是由Dijkstra等人提出来的银行家算法。操作系统按照银行家的规定为进程分配资源，进程首先提出对资源的最大需求量，当进程在执行中每次申请资源时，系统测试该进程已占用的资源与本次申请的资源数之和是否超过了该进程对资
源的最大需求量。若超过则拒绝分配资源，若没有超过，则系统再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。这样做，能保证在任何时刻至少有一个进程可以得到所需要的全部资源而执行结束，执行结束后归还的资源加入到系统的剩余资源中，这些资源又至少可以满足另一个进程的最大需求，于是，可以保证系统中所有进程都能在有限的时间内得到需要的全部资源。

## 死锁的检测与解除
**死锁检测的时机：**  
通常，死锁检测可以在任何一次资源分配后，也可以在每次调度后，或者利用定时器定时运行检测，还有一种方法是当系统中某个进程长期位于阻塞态或阻塞进程过多时，启动死锁检测程序。

**死锁检测的算法：** 死锁检测的算法依不同的系统而不同。

**死锁的解除方法：**  
（1）剥夺资源。经常使用的方法有：还原算法，即恢复计算结果和状态；建立检查点主要是用来恢复分配前的状态。  
（2）撤销进程。撤销死锁进程，将它们占有的资源分配给另一些死锁进程，直到死锁解除为止。  

## 资源分配图
资源分配图是一张有向图，一个系统资源分配图SRAG可定义为一个二元组，即SRAG＝（V，E），其中V是顶点的集合，而E是有向边的集合。  

**死锁定理：**  
（1）如果资源分配图中没有环路，则系统没有死锁。  
（2）如果资源分配图中出现了环路，则系统中可能存在死锁。  
①如果处于环路中的每个资源类中均只包含一个资源实例，则环路的存在即意味着死锁的存在。此时，环路是死锁的充分必要条件。  
②如果处于环路中的每个资源类中资源实例的个数不全为1，则环路的存在是产生死锁的必要条件而不是充分条件。  

**资源分配图化简方法：**  
（1）在资源分配图中，找出一个既非等待又非孤立的进程结点P1，由于P；可获得它所需要的全部资源，且运行完后释放它所占有的全部资源，故可在资源分配图中消去P1所死锁产生的原有的申请边和分配边，使之成为既无申请边又无分配边的孤立结点。  
（2）将P1所释放的资源分配给申请它们的进程，即在资源分配图中将这些进程对资源的申请边改为分配边。  
（3）重复（1）、（2）两步骤，直到找不到符合条件的进程结点。  
经过化简后，若能消去资源分配图中的所有边，使所有进程都成为孤立结点，则该图是可完全化简的；否则为不可化简的。

## 哲学家就餐问题
哲学家就餐问题是操作系统中关于进程同步与互斥的经典问题，也是涉及死锁的关键问题。
